package 深度优先搜索;

import java.util.LinkedList;

/**
 * 拓扑排序，判断此课程是不是有向无环图（DAG）
 * 拓扑排序是对DAG的顶点进行排序，使得每一条有向边（u,v）,均有u(在排序记录中)比v先出现。
 * 亦可理解为对某点v而言，只有当v所有当源店均出现了，v才出现。
 *
 * 通过课程当前置条件prerequisites可以得到课程安排图的 邻接矩阵 adjacency
 *
 * 可以采用：广度优先搜索和深度优先搜索解决这个问题
 */
public class Solution207课程表 {
    /**
     * 广度优先搜索
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程关系
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /* 记录每个课程的入度*/
        int[] indegrees = new int[numCourses];
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;
        }

        /* 将入度为0的课程加入到队列中*/
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.addLast(i);
            }
        }

        while (!queue.isEmpty()) {
            /*从队列首拿元素*/
            Integer pre = queue.removeFirst();
            /* 修完了一门课*/
            numCourses--;
            for (int[] req : prerequisites) {
                /* 要修req[1]需要先修req[0]*/
                if (req[1] != pre) {
                    continue;
                }
                if (--indegrees[req[0]] == 0) {
                    queue.addLast(req[0]);
                }
            }
        }
        return numCourses == 0;
    }
}
